/*
 * @lc app=leetcode.cn id=264 lang=cpp
 *
 * [264] 丑数 II
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int nthUglyNumber(int n)
    {
        if (n <= 5)
            return n;
        set<long long> s;
        s.insert(1);
        priority_queue<long long, vector<long long>, greater<long long>> q;
        q.push(1);

        long long ans = 1;
        vector<long long> factors = {2, 3, 5};
        for (long long i = 0; i < n; i++)
        {
            auto t = q.top();
            q.pop();
            ans = t;
            for(auto f : factors)
            {
                if(s.find(f * t) == s.end())
                {
                    s.insert(f * t);
                    q.push(f * t);
                }
            }
        }
        return ans;
    }
};
// long long main()
// {
//     Solution().nthUglyNumber(20);
//     return 0;
// }
// @lc code=end
